package com.learn.algorlthm;

/**
 * @classname:
 * @Description: 旋转数组的最小数字
 * @author: yfpu(fengpu.yang @ ucarinc.com)
 * @Date: 2018-07-09 15:06
 * 题目描述：
 *  把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转。输出旋转
 * 数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1.NOTE：给出的所有元素都大于0，若
 * 数组大小为0，请返回0.
 */
public class Learn11 {

    /**
     * 解题思路
     *  当nums[m] <= nums[h]的情况下，说明解在[l，m]之间，此时令h=m；否则解在[m+1, h]之间，令l=M+1.
     *  因为h的赋仩表达式为 h = m,因此循环条件应该为 l<h.
     */

    public static int minNumberInRotateArray(int[] nums) {
        if (nums.length == 0)
            return 0;
        int l = 0, h = nums.length - 1;
        while (l < h) {
            int m = l + (h - l) / 2;
            if (nums[m] <= nums[h])
                h = m;
            else
                l = m + 1;
        }
        return nums[l];
    }


}
